코딩테스트 복기 - 배열에서 특정 수보다 작은 수 중 가장 가까운 수를 찾는 방법(find nearest element than smaller one on the left side)
1. 문제 배열이 주어질때, 특정한 수보다 작으면서 가장 가까운 수를 찾고자 한다. 예를 들어 [3,1,2,10,5,6,4]가 주어질때, 10보다 작으면서 가까운 수는 바로 옆에 2와 5가 있다 이 경우 인덱스가 더 작은 2를 출력하고 싶고 1의 경우는 만족하는 원소가 없으므로 -1을 출력한다. 2. 풀이 - 왼쪽에서 더 작은 원소의 위치를 찾기 생각보다 어렵던데..? 그냥 많이 어려운데 적어도 생각나는건 $O(N^{2})$ 브루트 포스뿐.. 하지만 n이 10만이 넘어가는데 브루트 포스가 통과할리는 없을 것 같고 스택을 이용해서 O(N)에 효율적으로 풀 수 있다고 한다 알고리즘을 보면 의외로 간단하네.. 생각하기가 어렵지 일단 A의 i번째 원소에 대해 왼쪽에서 작으면서 가장 가까운 원소를 찾는다 그래서 ..
